Unless otherwise indicated herein, the materials described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Some databases may contain millions of records, resulting in many gigabytes of storage. For example, telecommunications companies maintain customer billing databases with billions of rows and terabytes of data. In order for a database to be useful and usable, it needs to be able to perform desired database operations, such as retrieval and storage, relatively quickly. As large databases may not be maintained entirely in memory, k-ary tree structures may be used to index the data and to provide fast access. For example, searching an unindexed and unsorted database containing n key values may necessitate a worst-case running time of O(n). In contrast, if the same data is indexed with a tree structure such as a k-ary tree structure, the same search operation takes time O(log n). Indexing large databases may significantly improve search performance.